#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Dec 30 10:12:12 2019

@author: yu
"""

# coding=GBK
import time as tm
from collections import defaultdict
import copy
import concurrent.futures


openT = {}
preNode = {}
deepD = {}
keysList = []

class oneway:
    def clear():
        openT.clear()
        preNode.clear()
        deepD.clear()
        keysList.clear()
    
    def __init__(self,loc_num,orgList):
        self.loc_num=loc_num
        self.orgList=orgList
        self.aimList=['0', '0', '0', '1', '2', '3', '4', '5', '6', '0', '0', '0']
        
    def exZero(self):
        dic={}
        for i in range(self.loc_num):
            if i%3==0 and i<3:
                dic[int(i)]=[int(i+1),int(i+3)]
            elif i%3==0 and i<self.loc_num-3:
                dic[int(i)]=[int(i-3),int(i+1),int(i+3)]
            elif i%3==0:
                dic[int(i)]=[int(i-3),int(i+1)]
            elif i%3==1 and i<3:
                dic[int(i)]=[int(i-1),int(i+1),int(i+3)]
            elif i%3==1 and i<self.loc_num-3:
                dic[int(i)]=[int(i-3),int(i-1),int(i+1),int(i+3)]
            elif i%3==1:
                dic[int(i)]=[int(i-3),int(i-1),int(i+1)]
            elif i%3==2 and i<3:
                dic[int(i)]=[int(i-1),int(i+3)]
            elif i%3==2 and i<self.loc_num-3:
                dic[int(i)]=[int(i-3),int(i-1),int(i+3)]
            else:
                dic[int(i)]=[int(i-1),int(i-3)]
        return dic
    @staticmethod
    def mhd(a, b):
        c = divmod(a, 3)  # 字符串第一位是0
        d = divmod(b, 3)
        g = abs(c[0] - d[0]) + abs(c[1] - d[1])
        return g
    
    @staticmethod
    def exc(a, i, j):
        b=copy.deepcopy(a)
        b[i] = a[j]
        b[j]=a[i]
        return b

    @staticmethod
    def whereIsZero(curString):
        a = []
        for i in range(len(curString)):
            if curString[i] == "0":
                a.append(i)
        return a

    
    def fn(self,curString, aimString, d):
        curList=curString.split('.')
        aimList=aimString.split('.')
        e = 0
        for i in range(0, len(curList)):
            if curList[i] != "0":
                if curList[i] != aimList[i]:
                    b = self.mhd(i, aimList.index(curList[i]))
                    e += b
    
        f = e + d
        return f


    # deepD需要记录字符串和其对应的步数
    # 查看不一样的两位数并返回非零的那一个
    @staticmethod
    def judgeEx(a, b):  # a和b是两个字符串，这个方程负责比较两个字符串并返回不是0的那个元素的值（不是位置
        for i in range(len(a)):
            if a[i] != b[i]:
                if a[i] != "0":
                    return a[i]
                else:
                    return b[i]
    def next_states(self,curList,zero):
        #for zero in self.whereIsZero(curList):
            #print('exZero[zero]=',exZero[zero])
        allDigits = []
        for i in self.exZero()[zero]:    
            if curList[i]!='0':
                allDigits.append(i)
        #print('chaJi=',chaJi)
        if allDigits != []:  # 如果差集不为空
            for digits in allDigits:  # 差集不为空，两个字符串交换字符生成新的字符串
                newList = self.exc(curList, zero, digits)
                newString=".".join(newList)
                if preNode.get(newString) == None:
                    deepD[newString] = deepD[curString] + 1  # 更新步数字典
                    openT[newString] = self.fn(newString, aimString, deepD[newString])
                    preNode[newString] = curString
        lst_steps = []
    def aStar(self):
        orgString='.'.join(self.orgList)
        aimString='.'.join(self.aimList)
        # 字典初始化
        deepD[orgString] = 0
        preNode[orgString] = -1  # 记录前驱节点
        openT[orgString] = self.fn(orgString, aimString, deepD[orgString])
        while True:
            curString = min(zip(openT.values(), openT.keys()))[1]
            curList=curString.split('.')
            del (openT[curString])
            if curString == aimString:
                break
            with concurrent.futures.ThreadPoolExecutor() as executor:
                noCar=[i for i in range(len(curList))]
                curListr=[curList]*6
                executor.map(self.nextStates,curListr,noCar)
            
        lst_steps.append(curString)
        while preNode[curString] != -1:  # 存入路径
            curString = preNode[curString]
            lst_steps.append(curString)
        lst_steps.reverse()
        return lst_steps


    def get_results(self):
        start = tm.time()
        printL = self.aStar()
        end = tm.time()
        
        time_consuming=end-start
        
        '''
        for k, v in finalSt.items():
            print("第" + str(k) + "步")
            
            for i in range(len(v)):
                v[i]=v[i].split('.')
                print(v[i][:3])
                print(v[i][3:6])
                print(v[i][6:9])
                print(v[i][9:12])
                print(v[i][12:])
                print("曼哈顿距离",self.fn('.'.join(v[i]),'.'.join(self.aimList),0))
                
                print("→")
        print("Total " + str(len(finalSt.items())) + " steps")
            
        print("Time consuming is "+str(end-start)+" seconds")
        '''
        return printL,time_consuming
    '''for i in range(len(c)):
        print("第" + str(i)+"步")
        print(c[i][:3])
        print(c[i][3:6])
        print(c[i][6:9])
        print(c[i][9:])
    print("用时"+str(end-start)+"秒")
    keysList=list(openT.keys())
    print(len(keysList))'''
# 000364105020 13 √
# 500431000260 16 √
# 040250000361 17 √
    '''
final_bubble_start,final_bubble_end= ['0', '0', '0', '14', '0', '15', '0', '4', '9', '3', '0', '0', '0', '0', '5'] ,['0', '0', '0', '15', '14', '4', '3', '9', '5', '0', '0', '0', '0', '0', '0']
ini_astar=oneway(len(final_bubble_start),final_bubble_start,final_bubble_end)
steps,time_consuming=ini_astar.get_results()
print('steps',steps,'time_consuming',time_consuming)


accu_steps=0
accu_time=0
final_bubble_start =['0', '0', '0', '0', '0', '12', '11', '0', '2', '6', '0', '8', '0', '0', '0'] 
final_bubble_end =['0', '0', '0', '12', '2', '6', '11', '0', '0', '0', '0', '8', '0', '0', '0']
ini_astar=oneway(len(final_bubble_start),final_bubble_start,final_bubble_end)
steps,time_consuming=ini_astar.get_results()
accu_steps+=steps
accu_time+=time_consuming
print('accu_steps',accu_steps,'accu_time',accu_time)
'''
'''
start_list= ['0', '3', '4', '0', '2', '0', '5', '6', '0', '1', '0', '0'] 
ini_astar=oneway(len(start_list),start_list)
printL,time_consuming=ini_astar.get_results()
diPoint = []
listA = []
s_count = 0
finalSt = defaultdict(list)
#print(finalSt.items())
for i in range(len(printL) - 1):  # 把所有的字符串遍历一下
    listA.append(judgeEx(printL[i].split('.'), printL[i + 1].split('.')))
#print(listA)
diPoint.append(listA[0])
for i in range(0, len(listA)):
    if listA[i] not in diPoint:
        finalSt[s_count].append(printL[i + 1])
        diPoint.append(listA[i])
    else:
        s_count += 1
        finalSt[s_count].append(printL[i + 1])
        diPoint.clear()
        diPoint.append(listA[i])

steps=len(finalSt.items())

print('time_consuming',time_consuming,'steps',steps)
'''